package cn.edu.jxau.test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Objects;

/**
 * 二叉查找树简单实现
 * 
 * @author 付大石
 */
public class BinarySearchTree<T extends Comparable<T>> {

    public static void main(String[] args) {

        BinarySearchTree<Integer> bst = new BinarySearchTree(new Integer[] { 23, 54, 12, 65, 37, 98, 34 });
        System.out.println(bst.contains(65));
        bst.delete(2);
        System.out.println(bst.contains(65));
        for (Integer item : bst.preOrder()) {
            System.out.print(item + " ");
        }
    }

    /**
     * 二叉查找树的根节点
     */
    private Node root;

    /**
     * 二叉查找树的节点数
     */
    private int size;

    public BinarySearchTree() {

    }

    public BinarySearchTree(T item) {

        Objects.requireNonNull(item, "参数item不能为null");
        this.root = new Node(item);
        this.size = 1;
    }

    /**
     * 用一个数组构造二叉查找树
     * 
     * @param arr
     */
    public BinarySearchTree(T[] arr) {

        Objects.requireNonNull(arr, "参数arr不能为null");
        for (T item : arr) {
            insert(item);
        }
    }

    public boolean contains(T item) {

        Objects.requireNonNull(item, "参数item不能为null");
        Node current = root;
        while (current != null) {
            int cmp = current.item.compareTo(item);
            if (cmp > 0) {
                current = current.left;
            } else if (cmp < 0) {
                current = current.right;
            } else {
                return true;
            }
        }
        return false;
    }

    /**
     * 向二叉查找树中插入一个item结点
     *
     * @param item
     */
    public void insert(T item) {

        // 参数校验 //
        Objects.requireNonNull(item);

        // 特殊情况处理 //
        if (root == null) {
            root = new Node(item);
            size++;
            return;
        }

        // 插入一个结点 //
        Node parent = null;
        Node current = root;
        while (current != null) {
            int cmp = current.item.compareTo(item);
            if (cmp > 0) {
                parent = current;
                current = current.left;
            } else if (cmp < 0) {
                parent = current;
                current = current.right;
            } else { // item结点已存在
                return;
            }
        }
        int cmp = parent.item.compareTo(item);
        if (cmp > 0) {
            parent.left = new Node(item);
        } else if (cmp < 0) {
            parent.right = new Node(item);
        }
        size++;
    }

    public int size() {
        return size;
    }

    /**
     * 前序遍历
     * 
     * @return
     */
    public Iterable<T> preOrder() {

        List<T> list = new ArrayList<>();
        preOrder(root, list);
        return list;
    }

    private void preOrder(Node node, List<T> list) {

        if (node == null) {
            return;
        }
        list.add(node.item);
        preOrder(node.left, list);
        preOrder(node.right, list);
    }

    /**
     * 中序遍历
     * 
     * @return
     */
    public Iterable<T> inOrder() {

        List<T> list = new ArrayList<>();
        inOrder(root, list);
        return list;
    }

    private void inOrder(Node node, List<T> list) {

        if (node == null) {
            return;
        }
        inOrder(node.left, list);
        list.add(node.item);
        inOrder(node.right, list);
    }

    /**
     * 后序遍历
     * 
     * @return
     */
    public Iterable<T> postOrder() {

        List<T> list = new ArrayList<>();
        postOrder(root, list);
        return list;
    }

    private void postOrder(Node node, List<T> list) {

        if (node == null) {
            return;
        }
        postOrder(node.left, list);
        postOrder(node.right, list);
        list.add(node.item);
    }

    public boolean isEmpty() {
        return root == null;
    }

    /**
     * 从根节点到item所经过的结点
     * 
     * @param item
     * @return
     */
    public Iterable<T> getPath(T item) {

        if (isEmpty()) {
            throw new RuntimeException("这是棵空树");
        }
        List<T> list = new ArrayList<>();
        Node current = root;
        while (current != null) {
            int cmp = current.item.compareTo(item);
            list.add(current.item);
            if (cmp > 0) {
                current = current.left;
            } else if (cmp < 0) {
                current = current.right;
            } else {
                return list;
            }
        }
        return Collections.emptyList();
    }

    public void delete(T item) {

        // 参数校验 //
        if (isEmpty()) {
            throw new RuntimeException("这是棵空树");
        }

        // 找到要删除的结点 //
        Node parent = null;
        Node current = root;
        while (current != null) {
            int cmp = current.item.compareTo(item);
            if (cmp > 0) {
                parent = current;
                current = current.left;
            } else if (cmp < 0) {
                parent = current;
                current = current.right;
            } else { // 成功找到结点
                break;
            }
        }
        if (current == null) { // 未找到结点
            return;
        }
        if (parent == null) { // 要删除根节点
            if (root.left != null && root.right != null) { // 左右子树均不为空
                Node min = minNode(root.right);
                min.right = deleteMin(root.right);
                min.left = root.left;
                root = min;
            } else if (root.left != null && root.right == null) { // 左子树不为空，右子树为空
                root = root.left;
            } else if (root.right != null && root.left == null) { // 右子树不为空，左子树为空
                root = root.right;
            } else { // 左右子树均为空
                root = null;
            }
            return;
        }
        int cmp = parent.item.compareTo(current.item); // 判断current是parent的左孩子还是parent的右孩子
        if (cmp > 0) { // current是parent的左孩子
            if (current.left != null && current.right != null) { // 左右子树均不为空
                Node min = minNode(current.right);
                min.right = deleteMin(current.right);
                min.left = current.left;
                parent.left = min;
            } else if (current.left != null && current.right == null) { // 左子树不为空，右子树为空
                parent.left = current.left;
            } else if (current.right != null && current.left == null) { // 右子树不为空，左子树为空
                parent.left = current.right;
            } else { // 左右子树均为空
                parent.left = null;
            }
        } else if (cmp < 0) { // current是parent的右孩子
            if (current.left != null && current.right != null) {
                Node min = minNode(current.right);
                min.right = deleteMin(current.right);
                min.left = current.left;
                parent.right = min;
            } else if (current.left != null && current.right == null) {
                parent.right = current.left;
            } else if (current.right != null && current.left == null) {
                parent.right = current.right;
            } else { // 左右子树均为空
                parent.right = null;
            }
        } else {
            // never go to here
        }
    }

    private Node minNode(Node node) {
        if (node.left == null) {
            return node;
        }
        return minNode(node.left);
    }

    private Node deleteMin(Node node) {

        if (node.left == null) {
            return node.right;
        }
        node.left = deleteMin(node.left);
        return node;
    }

    /**
     * 结点类
     * 
     * @author 付大石
     */
    private class Node {

        private T item;
        private Node left;
        private Node right;

        public Node(T item) {
            this.item = item;
        }
    }
}
